package datastructure.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-23
 */
public class PolandNotation {

    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";
        List<String> expressionList = toInfixExpression(expression);
        System.out.println(expressionList);
        List<String> psel = parseSuffixExpressionList(expressionList);
        System.out.println(psel);
    }

    /**
     * 将中缀表达式list转换后缀表达式list
     *
     * @param expressionList 中缀表达式list
     * @return 后缀表达式list
     */
    private static List<String> parseSuffixExpressionList(List<String> expressionList) {
        if (expressionList == null || expressionList.size() == 0){
            return null;
        }
        // 符号栈
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();

        for (String item : expressionList) {
            if (item.matches("\\d+")) {
                // 如果是数直接加入s2
                s2.add(item);
            } else if ("(".equals(item)) {
                s1.push(item);
            } else if (")".equals(item)) {
                while (!"(".equals(s1.peek())) {
                    // 如果是 ） 则依次弹出s1栈顶的运算符，并压入s2,直到遇见 （ 为止 ，此时丢弃 （
                    s2.add(s1.pop());
                }
                // 丢弃 （
                s1.pop();
            } else {
                // 当item的优先级小于等于s1栈顶运算符的优先级，将s1栈顶的运算符弹出并添加到s2
                while (s1.size() != 0 && Operation.getValue(item) <= Operation.getValue(s1.peek())) {
                    s2.add(s1.pop());
                }
                // 还需要将item压栈
                s1.push(item);
            }
        }

        // 依次将s1中的符号添加到s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 将表达式转换成list
     *
     * @param expression 表达式
     * @return list
     */
    private static List<String> toInfixExpression(String expression) {
        if ("".equals(expression) || expression == null) {
            return null;
        }
        List<String> expressionList = new ArrayList<>(expression.length());
        int i = 0;
        StringBuilder str;
        char c;
        do {
            c = expression.charAt(i);
            // 判断是否是符号
            if (c < 48 || c > 57) {
                // 符号直接添加
                expressionList.add(c + "");
                i++;
            } else {
                str = new StringBuilder();
                while (i < expression.length()) {
                    char ch = expression.charAt(i);
                    if (ch >= 48 && ch <= 57) {
                        // 多位数拼接
                        str.append(ch);
                        i++;
                    } else {
                        break;
                    }
                }
                expressionList.add(str.toString());
            }
        } while (i < expression.length());
        return expressionList;
    }
}

class Operation {

    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {

        int res = 0;
        switch (operation) {
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                break;
        }
        return res;
    }
}
